// 链队列

#include <stdio.h>
#include <malloc.h>

#define OK 1
#define ERROR 0

typedef int Status;
typedef int QElemType;  //队列中的元素类型

typedef struct QNode  //队列中的节点类型
{
    QElemType data;
    struct QNode *next;
} QNode, *QueuePtr;

typedef struct {
    QueuePtr front;
    QueuePtr rear;
} LinkQueue;   //定义连队列类型

Status InitQueue(LinkQueue &Q) {
    Q.front = (QueuePtr) malloc(sizeof(QNode));
    Q.front->next = NULL;
    if (!Q.front)
        return ERROR;
    Q.rear = Q.front;
    return OK;
}//初始化一个空队列，即分配头节点。头指针和尾指针初始化在头节点位置。成功返回OK，失败返回ERROR。

Status GetHead(LinkQueue Q, QElemType &e) {
    if (Q.rear == Q.front)
        return ERROR;
    e = Q.front->next->data;
    return OK;
}//获取队头元素的值并返回在e中，取值成功返回OK，失败返回ERROR

Status EnQueue(LinkQueue &Q, QElemType e) {
    QueuePtr p = (QueuePtr) malloc(sizeof(QNode));
    if (!p)
        return ERROR;
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
    return OK;
}//将元素e入队成为新的队尾元素

Status DeQueue(LinkQueue &Q, QElemType &e) {
    if (Q.rear == Q.front)
        return ERROR;
    QueuePtr p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if (Q.rear == p)
        Q.rear = Q.front;
    free(p);
    return OK;
}//将队头元素出队 ，其值返回在e中。出队成功返回OK，失败返回ERROR。

int QueueLength(LinkQueue Q) {
    QueuePtr p = Q.front;
    int i = 0;
    while (p != Q.rear) {
        p = p->next;
        i++;
    }
    return i;
}//求队列长度操作，即返回实际元素个数。
